Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm

摘要

Motivated by the observation that FIFO-based push-relabel algorithms are ableto outperform highest label-based variants on modern, large maximum flowproblem instances, we introduce an efficient implementation of the algorithmthat uses coarse-grained parallelism to avoid the problems of existing parallelapproaches. We demonstrate good relative and absolute speedups of our algorithmon a set of large graph instances taken from real-world applications. On amodern 40-core machine, our parallel implementation outperforms existingsequential implementations by up to a factor of 12 and other parallelimplementations by factors of up to 3.